package 力扣.树.后序遍历;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }
    public TreeNode(int _val) {
        val = _val;
    }
}
public class 遍历 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = null;
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        List<Integer> integers = postorderTraversal(root);
        postorderTraversal(root);
    }

    /**
       后序遍历：左右根 等左右子节点遍历完毕之后才能遍历根节点，
       ‘那么如何判断左右子节点是否为空呢？’
          解答：遍历root,每次将根节点的左子节点入栈，直到左节点为空。这样就等价于知道了左子节点为空
              而对于右子节点：有两种情况1、右子节点直接判断为空 2、右子节点判断不为空，此时我们要遍历又节点 这时我们发现等右子节点的
              所有孩子节点（包括自身节点）都遍历完毕之后，又如何让其父节点知道它的右子节点为空呢?
                 这里可以多申请一个节点pre,如果父节点的右子节点正好等于pre节点（root.right == pre） 则说明父节点的右子节点遍历完毕

     */
    // 为什么要使用pre? 详见上面的解释
    public static List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;//pre表示当前节点已经遍历过了
        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.add(root);
                root = root.left;
            }
            root = stack.peek();
            if (root.right == null || pre == root.right){
                list.add(root.val);
                pre = root;
                stack.pop();
                root = null;//巧妙
            }else {
                root = root.right;
            }
        }
        return list;
    }


    public List<Integer> postorderTraversal3(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        TreeNode pre = null;//表示当前节点遍历完毕
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.add(root);
                root = root.left;
            }
            //到达最左边节点的左子树（为空）

            TreeNode pop = stack.peek();
            //两种情况：1、右子树为空 2、右子树已经遍历完毕
            if (pop.right == null || pop.right == pre){
                ans.add(pop.val);
                stack.pop();
                pre = pop;
            }else{
                root = pop.right;
            }
        }
        return ans;
    }
}
